class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def maxProduct(self, root):
        d = {}
        self.max_val = - float('inf')

        def dfs1(node):
            left_val = 0
            right_val = 0
            if node.left:
                left_val = dfs1(node.left)
            if node.right:
                right_val = dfs1(node.right)
            d[node] = left_val + right_val + node.val
            return d[node]

        dfs1(root)

        def dfs2(node, now):
            now += node.val
            left_val = 0
            right_val = 0
            if node.left:
                left_val = d[node.left]
            if node.right:
                right_val = d[node.right]
            self.max_val = max(self.max_val, (now + left_val) * right_val, (now + right_val) * left_val)
            if now + left_val < right_val:
                dfs2(node.right, now + left_val)
            if now + right_val < left_val:
                dfs2(node.left, now + right_val)

        dfs2(root, 0)
        return self.max_val % (10 ** 9 + 7)


